﻿namespace Leetcode.N0132;

public class Solution
{
    public int MinCut(string s)
    {
        var minCuts = new int[s.Length];
        var flgs = new bool[s.Length][];

        for (int i = s.Length - 1; i >= 0; i--)
        {
            flgs[i] = new bool[s.Length];
            minCuts[i] = int.MaxValue;

            for (int j = i; j < s.Length; j++)
            {
                var r = this.Partition(s, i, j, minCuts, flgs);
                flgs[i][j] = r.flg;
                minCuts[i] = Math.Min(minCuts[i], r.minCut);
            }
        }

        return minCuts[0];
    }

    private (bool flg, int minCut) Partition(string s, int from, int to, int[] minCuts, bool[][] flgs)
    {
        var minCut = int.MaxValue;
        var flg = false;
        if (s[from] == s[to])
        {
            var sFromTo = s.Substring(from, to - from + 1);

            var subFrom = from + 1;
            var subTo = to - 1;
            flg = (subFrom > subTo || subFrom >= s.Length || subTo < 0) ? true : flgs[subFrom][subTo];

            if (flg)
            {
                if (to < s.Length - 1)
                {
                    minCut = minCuts[to + 1] + 1;

                }
                else
                {
                    minCut = 0;
                }
            }
        }

        return (flg, minCut);
    }
}